/*This code simulates the scienario where n links which are located in a single collision domains contend to send packets. 
Each link has one packet. Transmitters do not carrier sense. These are assumptions made in the following paper:
"Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels" by M. Bender et al.
The back-off strategy proposed in the paper (called loglog backoff) is compared with 802.11-style exponential back-off.*/

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <ctime>

using namespace std;

struct Node {
	int cw;
	int backoff;
	bool done;
	int rounds;
};

double backOff(int, int, int, double);

//The program takes three command line arguments to specify the number of nodes, 
//the initial contention window size, and the constant on loglog algorithm respectively.

int main(int argc, char* argv[]){
	int nodes = atoi(argv[1]);
	int cwSize = atoi(argv[2]);
	double const constantC = atof(argv[3]);

	double expTotal = backOff(1,nodes,cwSize, constantC);//exponential backoff
	 
	double loglogTotal = backOff(2,nodes,cwSize, constantC);//loglog backoff
	
	cout << "****************** SUMMARY *********************\n";
	cout <<"For " << nodes << " nodes and an initial window size of " << cwSize << endl;

	cout << "Exponential Backoff took " << expTotal << endl;
	cout << "Loglog Backoff took " << loglogTotal << endl;
	
	if (expTotal > loglogTotal)
		cout << "Loglog Backoff does " << 100* ((expTotal-loglogTotal)/loglogTotal) << "% better" <<  endl;
	else
		cout << "Exponential Backoff does " << 100* ((loglogTotal-expTotal)/expTotal) << "% better" <<  endl;
	cout << "*************************************************\n";

	return 0;
};

double backOff(int protocol, int nodesPopulation, int winSize, double C){
	srand(time(0));

	const int noOfNodes = winSize;//nodesPopulation;
	const int noOfRounds = 100000;
	int totalTime = 0;

	bool finished = false;
	int time = 0;
	Node nodes[noOfNodes];

	for (int k=0; k<noOfRounds; k++){
	for (int i=0; i< noOfNodes; i++){
		nodes[i].cw = winSize;//winSize;
		nodes[i].backoff = 1 + rand() % nodes[i].cw;
		nodes[i].done = false;
		nodes[i].rounds = ceil(C*(log2(log2(nodes[i].cw))));
	}

	while (!finished){
		time++;
		int firingNodes = 0;

		for (int i=0; i<noOfNodes; i++)
		{
			if (!nodes[i].done){
				nodes[i].backoff--;
				if (nodes[i].backoff == 0){
					firingNodes++;	
				}		
			}
		}
		
		if (firingNodes > 1){
			if (protocol == 1)
				for (int i=0; i<noOfNodes; i++)
					if (nodes[i].backoff == 0){
						nodes[i].cw *=2;
						nodes[i].backoff = 1+rand()%nodes[i].cw;
					}

			if (protocol == 2)
				for (int i=0; i<noOfNodes; i++){
					if (nodes[i].backoff == 0)
						if (nodes[i].rounds == 0){
							nodes[i].cw *= 2;
						nodes[i].rounds = ceil(C*(log2(log2(nodes[i].cw))));
					}

					nodes[i].backoff = 1+rand()%nodes[i].cw;
				}
		}

		if(firingNodes == 1){
			for (int i=0; i<noOfNodes; i++){
				if (nodes[i].backoff == 0){
					nodes[i].done = true;
				}
			}
		}

		finished = true;
		for (int i=0; i<noOfNodes; i++){
			if (!nodes[i].done){
				finished = false;
			}
		}

	}
		totalTime += time;
	}

	double exponentialBackoffTime = 0;
	double loglogBackoffTime = 0;

	return (double)totalTime/(double)noOfRounds;
}
